/*
 * Copyright (c) 2010, 2020, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.lang;

import java.lang.ClassValue.ClassValueMap;
import java.util.WeakHashMap;
import java.lang.ref.WeakReference;
import java.util.concurrent.atomic.AtomicInteger;

import sun.misc.Unsafe;

import static java.lang.ClassValue.ClassValueMap.probeHomeLocation;
import static java.lang.ClassValue.ClassValueMap.probeBackupLocations;

/**
 * 延迟地将计算值与（可能的）每个类型关联。
 * 例如，如果动态语言需要为在消息发送调用点遇到的每个类构造消息分派表，
 * 它可以使用 {@code ClassValue} 来缓存为每个遇到的类快速执行消息发送所需的信息。
 * @author John Rose, JSR 292 EG
 * @since 1.7
 */
public abstract class ClassValue<T> {
    /**
     * 唯一构造函数。（供子类构造函数调用，通常是隐式的。）
     */
    protected ClassValue() {
    }

    /**
     * 为此 {@code ClassValue} 计算给定类的派生值。
     * <p>
     * 此方法将在第一个使用 {@link #get get} 方法访问值的线程中调用。
     * <p>
     * 通常，此方法每个类最多调用一次，但如果调用了 {@link #remove remove}，
     * 则可能再次调用。
     * <p>
     * 如果此方法抛出异常，相应的 {@code get} 调用将异常终止并抛出该异常，
     * 且不会记录任何类值。
     *
     * @param type 必须计算其类值的类型
     * @return 与此 {@code ClassValue} 关联的新计算值，用于给定的类或接口
     * @see #get
     * @see #remove
     */
    protected abstract T computeValue(Class<?> type);

    /**
     * 返回给定类的值。如果尚未计算任何值，则通过调用 {@link #computeValue computeValue} 方法获得。
     * <p>
     * 在类上实际安装值是原子性执行的。此时，如果几个竞争线程已经计算了值，
     * 则选择一个值，并返回给所有竞争线程。
     * <p>
     * {@code type} 参数通常是一个类，但它可以是任何类型，
     * 如接口、基本类型（如 {@code int.class}）或 {@code void.class}。
     * <p>
     * 在没有 {@code remove} 调用的情况下，类值有一个简单的状态图：未初始化和已初始化。
     * 当进行 {@code remove} 调用时，值观察的规则更加复杂。
     * 有关更多信息，请参阅 {@link #remove remove} 的文档。
     *
     * @param type 必须计算或检索其类值的类型
     * @return 与此 {@code ClassValue} 关联的当前值，用于给定的类或接口
     * @throws NullPointerException 如果参数为 null
     * @see #remove
     * @see #computeValue
     */
    public T get(Class<?> type) {
        // non-racing this.hashCodeForCache : final int
        Entry<?>[] cache;
        Entry<T> e = probeHomeLocation(cache = getCacheCarefully(type), this);
        // racing e : current value <=> stale value from current cache or from stale cache
        // invariant:  e is null or an Entry with readable Entry.version and Entry.value
        if (match(e))
            // invariant:  No false positive matches.  False negatives are OK if rare.
            // The key fact that makes this work: if this.version == e.version,
            // then this thread has a right to observe (final) e.value.
            return e.value();
        // The fast path can fail for any of these reasons:
        // 1. no entry has been computed yet
        // 2. hash code collision (before or after reduction mod cache.length)
        // 3. an entry has been removed (either on this type or another)
        // 4. the GC has somehow managed to delete e.version and clear the reference
        return getFromBackup(cache, type);
    }

    /**
     * Removes the associated value for the given class.
     * 如果随后为同一个类{@linkplain #get 读取}此值，
     * 其值将通过调用其{@link #computeValue computeValue}方法重新初始化。
     * 这可能导致对给定类的{@code computeValue}方法的额外调用。
     * <p>
     * 为了解释{@code get}和{@code remove}调用之间的交互，
     * 我们必须建模类值的状态转换，以考虑
     * 未初始化和已初始化状态之间的交替。
     * 为此，从零开始按顺序编号这些状态，并注意
     * 未初始化（或已移除）状态用偶数编号，
     * 而已初始化（或重新初始化）状态用奇数编号。
     * <p>
     * 当线程{@code T}移除处于状态{@code 2N}的类值时，
     * 什么都不会发生，因为类值已经未初始化。
     * 否则，状态会原子地推进到{@code 2N+1}。
     * <p>
     * 当线程{@code T}查询处于状态{@code 2N}的类值时，
     * 线程首先尝试通过调用{@code computeValue}并安装结果值
     * 将类值初始化为状态{@code 2N+1}。
     * <p>
     * 当{@code T}尝试安装新计算的值时，
     * 如果状态仍然是{@code 2N}，类值将用
     * 计算的值初始化，推进到状态{@code 2N+1}。
     * <p>
     * 否则，无论新状态是偶数还是奇数，
     * {@code T}将丢弃新计算的值
     * 并重试{@code get}操作。
     * <p>
     * 丢弃和重试是一个重要的条件，
     * 因为否则{@code T}可能会安装
     * 一个灾难性的过时值。例如：
     * <ul>
     * <li>{@code T}调用{@code CV.get(C)}并看到状态{@code 2N}
     * <li>{@code T}快速计算一个时间相关的值{@code V0}并准备安装它
     * <li>{@code T}遇到不幸的分页或调度事件，长时间休眠
     * <li>...与此同时，{@code T2}也调用{@code CV.get(C)}并看到状态{@code 2N}
     * <li>{@code T2}快速计算一个类似的时间相关值{@code V1}并将其安装在{@code CV.get(C)}上
     * <li>{@code T2}（或第三个线程）然后调用{@code CV.remove(C)}，撤销{@code T2}的工作
     * <li>{@code T2}的前述操作重复几次
     * <li>同时，相关的计算值随时间变化：{@code V1}、{@code V2}、...
     * <li>...与此同时，{@code T}醒来并尝试安装{@code V0}；<em>这必须失败</em>
     * </ul>
     * 我们可以假设在上述场景中{@code CV.computeValue}使用锁来正确
     * 观察时间相关状态，因为它计算{@code V1}等。
     * 这并不能消除过时值的威胁，因为在{@code T}中{@code computeValue}返回
     * 和安装新值之间存在时间窗口。在此期间不可能进行用户同步。
     *
     * @param type 必须移除其类值的类型
     * @throws NullPointerException 如果参数为null
     */
    public void remove(Class<?> type) {
        ClassValueMap map = getMap(type);
        map.removeEntry(this);
    }

    // Possible functionality for JSR 292 MR 1
    /*public*/ void put(Class<?> type, T value) {
        ClassValueMap map = getMap(type);
        map.changeEntry(this, value);
    }

    /// --------
    /// Implementation...
    /// --------

    /** 返回缓存（如果存在），否则返回一个虚拟的空缓存。 */
    private static Entry<?>[] getCacheCarefully(Class<?> type) {
        // racing type.classValueMap{.cacheArray} : null => new Entry[X] <=> new Entry[Y]
        ClassValueMap map = type.classValueMap;
        if (map == null)  return EMPTY_CACHE;
        Entry<?>[] cache = map.getCache();
        return cache;
        // invariant:  returned value is safe to dereference and check for an Entry
    }

    /** 所有Class实例使用的初始单元素空缓存。绝不能被填充。 */
    private static final Entry<?>[] EMPTY_CACHE = { null };

    /**
     * ClassValue.get的慢速尾部，在缓存的附近位置重试，
     * 或获取慢速锁并检查哈希表。
     * 仅在第一次探测为空或发生冲突时调用。
     * 这是一个单独的方法，因此编译器可以独立处理它。
     */
    private T getFromBackup(Entry<?>[] cache, Class<?> type) {
        Entry<T> e = probeBackupLocations(cache, this);
        if (e != null)
            return e.value();
        return getFromHashMap(type);
    }

    // 用于抑制(T)强制转换警告的技巧，这是一个无操作。
    @SuppressWarnings("unchecked")
    Entry<T> castEntry(Entry<?> e) { return (Entry<T>) e; }

    /** 当get的快速路径失败且缓存重新探测也失败时调用。
     */
    private T getFromHashMap(Class<?> type) {
        // 故障安全恢复是回退到底层的classValueMap。
        ClassValueMap map = getMap(type);
        for (;;) {
            Entry<T> e = map.startEntry(this);
            if (!e.isPromise())
                return e.value();
            try {
                // 尝试为承诺版本创建真实条目。
                e = makeEntry(e.version(), computeValue(type));
            } finally {
                // 无论computeValue抛出异常还是正常返回，
                // 确保移除空条目。
                e = map.finishEntry(this, e);
            }
            if (e != null)
                return e.value();
            // 否则重试，以防竞争线程调用了remove（所以e == null）
        }
    }

    /** 检查e是否非空、匹配此ClassValue且是活跃的。 */
    boolean match(Entry<?> e) {
        // 竞争e.version：null（空白）=> 唯一版本令牌 => null（GC版本）
        // 非竞争this.version：v1 => v2 => ...（更新从volatile忠实读取）
        return (e != null && e.get() == this.version);
        // 不变量：版本匹配无假阳性。Null对于假阴性是可以的。
        // 不变量：如果版本匹配，则e.value是可读的（在Entry.<init>中最终设置）
    }

    /** 用于访问Class.classValueMap.cacheArray的内部哈希码。 */
    final int hashCodeForCache = nextHashCode.getAndAdd(HASH_INCREMENT) & HASH_MASK;

    /** hashCodeForCache的值流。参见ThreadLocal中的类似结构。 */
    private static final AtomicInteger nextHashCode = new AtomicInteger();

    /** 适用于2的幂次表。参见ThreadLocal中的类似结构。 */
    private static final int HASH_INCREMENT = 0x61c88647;

    /** 掩码哈希码使其为正但不太大，以防止回绕。 */
    static final int HASH_MASK = (-1 >>> 2);

    /**
     * 从ClassValueMap检索此对象的私有键。
     */
    static class Identity {
    }
    /**
     * 此ClassValue的身份，表示为不透明对象。
     * 主对象{@code ClassValue.this}是不正确的，因为
     * 子类可能重写{@code ClassValue.equals}，这
     * 可能会混淆ClassValueMap中的键。
     */
    final Identity identity = new Identity();

    /**
     * 从缓存检索此类值的当前版本。
     * 任意数量的computeValue调用都可以与一个版本关联缓存。
     * 但当执行remove（在任何类型上）时版本会改变。
     * 版本更改通过将受影响的ClassValue的所有缓存条目标记为过时
     * 来使其失效。过时的缓存条目不会强制再次调用
     * computeValue，但它们确实需要同步访问后备映射。
     * <p>
     * ClassValue上所有用户可见的状态更改都在
     * ClassValueMap的同步方法内的锁下进行。
     * 当this.version被提升到新令牌时，
     * 读取器（ClassValue.get的）会收到此类状态更改的通知。
     * 此变量必须是volatile的，以便非同步读取器
     * 能够无延迟地接收通知。
     * <p>
     * 如果version不是volatile的，一个线程T1可能持续持有
     * 过时值this.value == V1，而另一个线程T2推进
     * （在锁下）到this.value == V2。这通常是无害的，
     * 但如果T1和T2通过其他通道因果交互，使得
     * T1的进一步操作被约束（在JMM中）在
     * V2事件之后发生，那么T1对V1的观察将是错误的。
     * <p>
     * 使this.version为volatile的实际效果是它不能
     * 被（优化JIT）提升出循环或以其他方式缓存。
     * 某些机器可能还需要在this.version之前执行屏障指令。
     */
    private volatile Version<T> version = new Version<>(this);
    Version<T> version() { return version; }
    void bumpVersion() { version = new Version<>(this); }
    static class Version<T> {
        private final ClassValue<T> classValue;
        private final Entry<T> promise = new Entry<>(this);
        Version(ClassValue<T> classValue) { this.classValue = classValue; }
        ClassValue<T> classValue() { return classValue; }
        Entry<T> promise() { return promise; }
        boolean isLive() { return classValue.version() == this; }
    }

    /** 通过ClassValue将值绑定到类的一个绑定。
     *  状态有：<ul>
     *  <li> 如果value == Entry.this则为promise（承诺）
     *  <li> 否则如果version == null则为dead（死亡）
     *  <li> 否则如果version != classValue.version则为stale（过时）
     *  <li> 否则为live（活跃） </ul>
     *  承诺永远不会放入缓存；它们只在
     *  computeValue调用进行时存在于后备映射中。
     *  一旦条目变得过时，它可以随时重置
     *  为死亡状态。
     */
    static class Entry<T> extends WeakReference<Version<T>> {
        final Object value;  // 通常是T类型，但有时是(Entry)this
        Entry(Version<T> version, T value) {
            super(version);
            this.value = value;  // 对于常规条目，value是T类型
        }
        private void assertNotPromise() { assert(!isPromise()); }
        /** 用于创建承诺。 */
        Entry(Version<T> version) {
            super(version);
            this.value = this;  // 对于承诺，value不是T类型，而是Entry！
        }
        /** 获取值。此条目不能是承诺。 */
        @SuppressWarnings("unchecked")  // 如果!isPromise，类型是T
        T value() { assertNotPromise(); return (T) value; }
        boolean isPromise() { return value == this; }
        Version<T> version() { return get(); }
        ClassValue<T> classValueOrNull() {
            Version<T> v = version();
            return (v == null) ? null : v.classValue();
        }
        boolean isLive() {
            Version<T> v = version();
            if (v == null)  return false;
            if (v.isLive())  return true;
            clear();
            return false;
        }
        Entry<T> refreshVersion(Version<T> v2) {
            assertNotPromise();
            @SuppressWarnings("unchecked")  // if !isPromise, type is T
            Entry<T> e2 = new Entry<>(v2, (T) value);
            clear();
            // value = null -- 调用者必须丢弃
            return e2;
        }
        static final Entry<?> DEAD_ENTRY = new Entry<>(null, null);
    }

    /** 返回与此类型关联的后备映射。 */
    private static ClassValueMap getMap(Class<?> type) {
        // 竞争type.classValueMap：null（空白）=> 唯一ClassValueMap
        // 如果观察到null，则创建映射（延迟、同步、唯一）
        // 对该映射的所有进一步访问都是同步的
        ClassValueMap map = type.classValueMap;
        if (map != null)  return map;
        return initializeMap(type);
    }

    private static final Object CRITICAL_SECTION = new Object();
    private static final Unsafe UNSAFE = Unsafe.getUnsafe();
    private static ClassValueMap initializeMap(Class<?> type) {
        ClassValueMap map;
        synchronized (CRITICAL_SECTION) {  // 私有对象以避免死锁
            // 每种类型大约发生一次
            if ((map = type.classValueMap) == null) {
                map = new ClassValueMap(type);
                // 在构造后和发布前放置Store屏障以模拟
                // 包含final字段的ClassValueMap。这确保它可以
                // 安全地发布到非volatile字段Class.classValueMap中，
                // 因为对ClassValueMap字段的存储不会被重新排序
                // 到对字段type.classValueMap的存储之后发生
                UNSAFE.storeFence();

                type.classValueMap = map;
            }
        }
            return map;
        }

    static <T> Entry<T> makeEntry(Version<T> explicitVersion, T value) {
        // 注意explicitVersion可能与this.version不同。
        return new Entry<>(explicitVersion, value);

        // 一旦Entry被放入缓存，值将通过
        // 数据竞争（如Java内存模型定义）可达。
        // 假设值对象本身可以被多个线程安全读取，
        // 这种竞争是良性的。这取决于用户。
        //
        // entry和version字段本身可以通过
        // 竞争安全读取，因为它们要么是final的，要么有受控状态。
        // 如果从entry到version的指针仍然为null，
        // 或者如果version立即死亡并被置空，
        // 读取器将采用慢速路径并在锁下重试。
    }

    // 以下类也可以是顶级和非公共的：

    /** 所有ClassValue相对于单个给定类型的后备映射。
     *  为每个对(ClassValue cv, Class type)提供完全序列化的"真实状态"。
     *  还管理非序列化的快速路径缓存。
     */
    static class ClassValueMap extends WeakHashMap<ClassValue.Identity, Entry<?>> {
        private final Class<?> type;
        private Entry<?>[] cacheArray;
        private int cacheLoad, cacheLoadLimit;

        /** 首次与任何ClassValue一起使用时为每种类型初始分配的条目数。
         *  使其比Class和ClassValueMap对象本身小得多是没有意义的。
         *  必须是2的幂。
         */
        private static final int INITIAL_ENTRIES = 32;

        /** 为ClassValue构建相对于给定类型的后备映射。
         *  同时，创建一个空缓存数组并将其安装在类上。
         */
        ClassValueMap(Class<?> type) {
            this.type = type;
            sizeCache(INITIAL_ENTRIES);
        }

        Entry<?>[] getCache() { return cacheArray; }

        /** 启动查询。如果还没有值，则存储承诺（占位符）。 */
        synchronized
        <T> Entry<T> startEntry(ClassValue<T> classValue) {
            @SuppressWarnings("unchecked")  // 一个映射包含所有值类型<T>的条目
            Entry<T> e = (Entry<T>) get(classValue.identity);
            Version<T> v = classValue.version();
            if (e == null) {
                e = v.promise();
                // 承诺的存在意味着v有一个值正在等待。
                // 最终，finishEntry将覆盖承诺。
                put(classValue.identity, e);
                // 注意承诺永远不会进入缓存！
                return e;
            } else if (e.isPromise()) {
                // 其他人已经问了同样的问题。
                // 让竞争开始！
                if (e.version() != v) {
                    e = v.promise();
                    put(classValue.identity, e);
                }
                return e;
            } else {
                // 这里已经有一个完成的条目；报告它
                if (e.version() != v) {
                    // 这里有一个过时但有效的条目；让它重新变得新鲜。
                    // 一旦条目在哈希表中，我们不关心它的版本是什么。
                    e = e.refreshVersion(v);
                    put(classValue.identity, e);
                }
                // 添加到缓存，以便下次启用快速路径。
                checkCacheLoad();
                addToCache(classValue, e);
                return e;
            }
        }

        /** 完成查询。覆盖匹配的占位符。丢弃过时的传入值。 */
        synchronized
        <T> Entry<T> finishEntry(ClassValue<T> classValue, Entry<T> e) {
            @SuppressWarnings("unchecked")  // one map has entries for all value types <T>
            Entry<T> e0 = (Entry<T>) get(classValue.identity);
            if (e == e0) {
                // 我们可以在异常处理期间到达这里，从computeValue展开。
                assert(e.isPromise());
                remove(classValue.identity);
                return null;
            } else if (e0 != null && e0.isPromise() && e0.version() == e.version()) {
                // 如果e0匹配预期条目，则在之前的startEntry和现在之间
                // 没有remove调用。所以现在覆盖e0。
                Version<T> v = classValue.version();
                if (e.version() != v)
                    e = e.refreshVersion(v);
                put(classValue.identity, e);
                // Add to the cache, to enable the fast path, next time.
                checkCacheLoad();
                addToCache(classValue, e);
                return e;
            } else {
                // 某种不匹配；调用者必须重试。
                return null;
            }
        }

        /** 移除条目。 */
        synchronized
        void removeEntry(ClassValue<?> classValue) {
            Entry<?> e = remove(classValue.identity);
            if (e == null) {
                // 未初始化，且没有对computeValue的待处理调用。无变化。
            } else if (e.isPromise()) {
                // 状态未初始化，有对finishEntry的待处理调用。
                // 由于在这种状态下remove是无操作，通过将承诺
                // 放回映射中来保持承诺。
                put(classValue.identity, e);
            } else {
                // 处于初始化状态。向前推进，并去初始化。
                classValue.bumpVersion();
                // 使此家伙的所有缓存元素变得过时。
                removeStaleEntries(classValue);
            }
        }

        /** 更改条目的值。 */
        synchronized
        <T> void changeEntry(ClassValue<T> classValue, T value) {
            @SuppressWarnings("unchecked")  // one map has entries for all value types <T>
            Entry<T> e0 = (Entry<T>) get(classValue.identity);
            Version<T> version = classValue.version();
            if (e0 != null) {
                if (e0.version() == version && e0.value() == value)
                    // 无值变化 => 不需要版本变化
                    return;
                classValue.bumpVersion();
                removeStaleEntries(classValue);
            }
            Entry<T> e = makeEntry(version, value);
            put(classValue.identity, e);
            // Add to the cache, to enable the fast path, next time.
            checkCacheLoad();
            addToCache(classValue, e);
        }

        /// --------
        /// 缓存管理。
        /// --------

        // 静态方法不需要同步。

        /** 在给定（哈希）位置加载缓存条目。 */
        static Entry<?> loadFromCache(Entry<?>[] cache, int i) {
            // 非竞争cache.length：常量
            // 竞争cache[i & (mask)]：null <=> Entry
            return cache[i & (cache.length-1)];
            // 不变量：返回值为null或构造良好（准备匹配）
        }

        /** 在缓存中查找给定ClassValue的主位置。 */
        static <T> Entry<T> probeHomeLocation(Entry<?>[] cache, ClassValue<T> classValue) {
            return classValue.castEntry(loadFromCache(cache, classValue.hashCodeForCache));
        }

        /** 鉴于第一次探测是冲突，在附近位置重试。 */
        static <T> Entry<T> probeBackupLocations(Entry<?>[] cache, ClassValue<T> classValue) {
            if (PROBE_LIMIT <= 0)  return null;
            // 在一系列槽中仔细探测缓存。
            int mask = (cache.length-1);
            int home = (classValue.hashCodeForCache & mask);
            Entry<?> e2 = cache[home];  // 受害者，如果我们找到真正的家伙
            if (e2 == null) {
                return null;   // 如果家里没人，无需搜索附近
            }
            // 假设!classValue.match(e2)，但由于竞争不断言
            int pos2 = -1;
            for (int i = home + 1; i < home + PROBE_LIMIT; i++) {
                Entry<?> e = cache[i & mask];
                if (e == null) {
                    break;   // 只在非空运行中搜索
                }
                if (classValue.match(e)) {
                    // 将冲突条目e2（来自cache[home]）重新定位到第一个空槽
                    cache[home] = e;
                    if (pos2 >= 0) {
                        cache[i & mask] = Entry.DEAD_ENTRY;
                    } else {
                        pos2 = i;
                    }
                    cache[pos2 & mask] = ((entryDislocation(cache, pos2, e2) < PROBE_LIMIT)
                                          ? e2                  // 如果合适就把e2放在这里
                                          : Entry.DEAD_ENTRY);
                    return classValue.castEntry(e);
                }
                // 记住第一个空槽（如果有的话）：
                if (!e.isLive() && pos2 < 0)  pos2 = i;
            }
            return null;
        }

        /** e偏离位置多远？ */
        private static int entryDislocation(Entry<?>[] cache, int pos, Entry<?> e) {
            ClassValue<?> cv = e.classValueOrNull();
            if (cv == null)  return 0;  // 条目不是活跃的！
            int mask = (cache.length-1);
            return (pos - cv.hashCodeForCache) & mask;
        }

        /// --------
        /// 此行以下的所有函数都是私有的，并假设同步访问。
        /// --------

        private void sizeCache(int length) {
            assert((length & (length-1)) == 0);  // 必须是2的幂
            cacheLoad = 0;
            cacheLoadLimit = (int) ((double) length * CACHE_LOAD_LIMIT / 100);
            cacheArray = new Entry<?>[length];
        }

        /** 如果可能，确保缓存负载保持在其限制以下。 */
        private void checkCacheLoad() {
            if (cacheLoad >= cacheLoadLimit) {
                reduceCacheLoad();
            }
        }
        private void reduceCacheLoad() {
            removeStaleEntries();
            if (cacheLoad < cacheLoadLimit)
                return;  // 胜利
            Entry<?>[] oldCache = getCache();
            if (oldCache.length > HASH_MASK)
                return;  // 失败
            sizeCache(oldCache.length * 2);
            for (Entry<?> e : oldCache) {
                if (e != null && e.isLive()) {
                    addToCache(e);
                }
            }
        }

        /** 移除给定范围内的过时条目。
         *  应在Map锁下执行。
         */
        private void removeStaleEntries(Entry<?>[] cache, int begin, int count) {
            if (PROBE_LIMIT <= 0)  return;
            int mask = (cache.length-1);
            int removed = 0;
            for (int i = begin; i < begin + count; i++) {
                Entry<?> e = cache[i & mask];
                if (e == null || e.isLive())
                    continue;  // 跳过null和活跃条目
                Entry<?> replacement = null;
                if (PROBE_LIMIT > 1) {
                    // 避免破坏非空运行
                    replacement = findReplacement(cache, i);
                }
                cache[i & mask] = replacement;
                if (replacement == null)  removed += 1;
            }
            cacheLoad = Math.max(0, cacheLoad - removed);
        }

        /** 清除缓存槽有断开后续条目与非空运行头部连接的风险，
         *  这将允许通过重新探测找到它们。找到cache[begin]之后的
         *  条目来填补空洞，如果不需要则返回null。
         */
        private Entry<?> findReplacement(Entry<?>[] cache, int home1) {
            Entry<?> replacement = null;
            int haveReplacement = -1, replacementPos = 0;
            int mask = (cache.length-1);
            for (int i2 = home1 + 1; i2 < home1 + PROBE_LIMIT; i2++) {
                Entry<?> e2 = cache[i2 & mask];
                if (e2 == null)  break;  // 非空运行结束。
                if (!e2.isLive())  continue;  // 反正注定要失败。
                int dis2 = entryDislocation(cache, i2, e2);
                if (dis2 == 0)  continue;  // e2已经最优放置
                int home2 = i2 - dis2;
                if (home2 <= home1) {
                    // e2可以替换cache[home1]处的条目
                    if (home2 == home1) {
                        // 将e2准确放在它应该在的地方。
                        haveReplacement = 1;
                        replacementPos = i2;
                        replacement = e2;
                    } else if (haveReplacement <= 0) {
                        haveReplacement = 0;
                        replacementPos = i2;
                        replacement = e2;
                    }
                    // 继续进行，这样我们可以偏爱更大的位移。
                }
            }
            if (haveReplacement >= 0) {
                if (cache[(replacementPos+1) & mask] != null) {
                    // 保守一点，避免破坏非空运行。
                    cache[replacementPos & mask] = (Entry<?>) Entry.DEAD_ENTRY;
                } else {
                    cache[replacementPos & mask] = null;
                    cacheLoad -= 1;
                }
            }
            return replacement;
        }

        /** 移除classValue附近范围内的过时条目。 */
        private void removeStaleEntries(ClassValue<?> classValue) {
            removeStaleEntries(getCache(), classValue.hashCodeForCache, PROBE_LIMIT);
        }

        /** 移除所有地方的所有过时条目。 */
        private void removeStaleEntries() {
            Entry<?>[] cache = getCache();
            removeStaleEntries(cache, 0, cache.length + PROBE_LIMIT - 1);
        }

        /** 将给定条目添加到缓存的主位置，除非它已过时。 */
        private <T> void addToCache(Entry<T> e) {
            ClassValue<T> classValue = e.classValueOrNull();
            if (classValue != null)
                addToCache(classValue, e);
        }

        /** 将给定条目添加到缓存的主位置。 */
        private <T> void addToCache(ClassValue<T> classValue, Entry<T> e) {
            if (PROBE_LIMIT <= 0)  return;  // 不填充缓存
            // 将e添加到缓存。
            Entry<?>[] cache = getCache();
            int mask = (cache.length-1);
            int home = classValue.hashCodeForCache & mask;
            Entry<?> e2 = placeInCache(cache, home, e, false);
            if (e2 == null)  return;  // 完成
            if (PROBE_LIMIT > 1) {
                // 尝试将e2移动到其探测范围内的其他地方
                int dis2 = entryDislocation(cache, home, e2);
                int home2 = home - dis2;
                for (int i2 = home2; i2 < home2 + PROBE_LIMIT; i2++) {
                    if (placeInCache(cache, i2 & mask, e2, true) == null) {
                        return;
                    }
                }
            }
            // 注意：此时，e2只是从缓存中丢弃。
        }

        /** 存储给定条目。更新cacheLoad，并返回任何活跃受害者。
         *  '温和地'意味着返回自身而不是移位活跃受害者。
         */
        private Entry<?> placeInCache(Entry<?>[] cache, int pos, Entry<?> e, boolean gently) {
            Entry<?> e2 = overwrittenEntry(cache[pos]);
            if (gently && e2 != null) {
                // 不覆盖活跃条目
                return e;
            } else {
                cache[pos] = e;
                return e2;
            }
        }

        /** 注意即将被覆盖的条目。
         *  如果它不是活跃的，静默地用null替换它。
         *  如果它是实际的null，增加cacheLoad，
         *  因为调用者将在其位置存储某些东西。
         */
        private <T> Entry<T> overwrittenEntry(Entry<T> e2) {
            if (e2 == null)  cacheLoad += 1;
            else if (e2.isLive())  return e2;
            return null;
        }

        /** 调整大小前缓存的百分比加载。 */
        private static final int CACHE_LOAD_LIMIT = 67;  // 0..100
        /** 尝试的最大探测次数。 */
        private static final int PROBE_LIMIT      =  6;       // 1..
        // 注意：设置PROBE_LIMIT=0以禁用所有快速路径。
    }
}
